#define SORT_TYPE int
#define int64_t int
#define SORT_CMP(x, y)  ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))

static __inline int64_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x, const size_t size)
{
	int64_t l, c, r;
	SORT_TYPE cx;
	l = 0;
	r = size - 1;
	c = r >> 1;

	/* check for out of bounds at the beginning. */
	if (SORT_CMP(x, dst[0]) < 0) {
		return 0;
	}
	else if (SORT_CMP(x, dst[r]) > 0) {
		return r;
	}

	cx = dst[c];
	while (1) {
		const int val = SORT_CMP(x, cx);
		if (val < 0) {
			if (c - l <= 1) return c;
			r = c;
		}
		else { /* allow = for stability. The binary search favors the right. */
			if (r - c <= 1) return c + 1;
			l = c;
		}
		c = l + ((r - l) >> 1);
		cx = dst[c];
	}
}

/* Binary insertion sort, but knowing that the first "start" entries are sorted.  Used in timsort. */
static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size) {
	int64_t i;
	for (i = start; i < size; i++) {
		int64_t j;
		SORT_TYPE x;
		int64_t location;
		/* If this entry is already correct, just move along */
		if (SORT_CMP(dst[i - 1], dst[i]) <= 0) {
			continue;
		}

		/* Else we need to find the right place, shift everything over, and squeeze in */
		x = dst[i];
		location = BINARY_INSERTION_FIND(dst, x, i);
		for (j = i - 1; j >= location; j--) {
			dst[j + 1] = dst[j];
		}
		dst[location] = x;
	}
}

/* Binary insertion sort */
void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size) {
	BINARY_INSERTION_SORT_START(dst, 1, size);
}


void MERGE_SORT(SORT_TYPE *dst, int size) {
	const int64_t middle = size / 2;
	SORT_TYPE * newdst = (int*)calloc(size, sizeof(int));
	int64_t out = 0;
	int64_t i = 0;
	int64_t j = middle;

	if (size < 16) {
		BINARY_INSERTION_SORT(dst, size);
		return;
	}

	MERGE_SORT(dst, middle);
	MERGE_SORT(&dst[middle], size - middle);

	while (out != size) {
		if (i < middle) {
			if (j < size) {
				if (SORT_CMP(dst[i], dst[j]) <= 0) {
					newdst[out] = dst[i++];
				}
				else {
					newdst[out] = dst[j++];
				}
			}
			else {
				newdst[out] = dst[i++];
			}
		}
		else {
			newdst[out] = dst[j++];
		}
		out++;
	}
	memcpy(dst, newdst, size * sizeof(SORT_TYPE));
}